package main

import (
	"container/list"
	"fmt"
)

type LRUCache struct {
	cap int
	l   *list.List
	m   map[int]*list.Element
}

type Pair struct {
	key   int
	value int
}

func New(cap int) *LRUCache {
	return &LRUCache{
		cap: cap,
		l:   list.New(),
		m:   make(map[int]*list.Element),
	}
}

func (this *LRUCache) Get(key int) (int, bool) {
	if node, ok := this.m[key]; ok {
		this.l.MoveToFront(node)
		return node.Value.(Pair).value, true
	}

	return 0, false
}

func (this *LRUCache) Set(key int, value int) {
	if node, ok := this.m[key]; ok {
		this.l.MoveToFront(node)
		node.Value = Pair{
			key:   key,
			value: value,
		}
		return
	} else {
		if this.l.Len() == this.cap {
			back := this.l.Back()
			key := back.Value.(Pair).key
			this.l.Remove(back)
			delete(this.m, key)
		}

		node := this.l.PushFront(Pair{
			key:   key,
			value: value,
		})
		this.m[key] = node
	}
}

func main() {

	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1))
	cache.Put(3, 3)
	cache.Get(2)
	cache.Put(4, 4) // evicts key 1
	cache.Get(1)    // returns -1 (not found)
	cache.Get(3)    // returns 3
	cache.Get(4)    // returns 4
	fmt.Println(cache.Get(4))
}
